abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...

, the conjugacy problem for a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...

''G'' with a given

presentation A presentation conveys information from a speaker to an audience. Presentations are typically demonstrations, introduction, lecture, or speech meant to inform, persuade, inspire, motivate, build goodwill, or present a new idea/product. Presenta ...

is the

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

of determining, given two words ''x'' and ''y'' in ''G'', whether or not they represent conjugate elements of ''G''. That is, the problem is to determine whether there exists an element ''z'' of ''G'' such that :

y = zxz^.\,\!

The conjugacy problem is also known as the transformation problem. The conjugacy problem was identified by

Max Dehn Max Wilhelm Dehn (November 13, 1878 – June 27, 1952) was a German mathematician most famous for his work in geometry, topology and geometric group theory. Born to a Jewish family in Germany, Dehn's early life and career took place in Germany. ...

in 1911 as one of the fundamental decision problems in group theory; the other two being the word problem and the isomorphism problem. The conjugacy problem contains the word problem as a special case: if ''x'' and ''y'' are words, deciding if they are the same word is equivalent to deciding if

xy^

is the identity, which is the same as deciding if it's conjugate to the identity. In 1912 Dehn gave an algorithm that solves both the word and conjugacy problem for the

fundamental group In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of ...

s of closed orientable two-dimensional

manifold In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a n ...

s of genus greater than or equal to 2 (the genus 0 and genus 1 cases being trivial). It is known that the conjugacy problem is undecidable for many classes of groups. Classes of group presentations for which it is known to be soluble include: * free groups (no defining relators) * one-relator groups with torsion * braid groups * knot groups * finitely presented conjugacy separable groups * finitely generated abelian groups (relators include all commutators) * Gromov-hyperbolic groups * biautomatic groups * CAT(0) groups *

Fundamental group In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of ...

s of geometrizable 3-manifolds

References

* * * * * * * * Group theory {{Abstract-algebra-stub